package com.yoshino.leetcode.improve40.threeteenth;

import java.util.Stack;

class Solution {
    // 装水最大问题
    public int largestRectangleArea2(int[] heights) {
        // 单调栈，记录左边界
        Stack<Integer> stack = new Stack<>();
        // 防止为空
        int res = 0;
        stack.push(-1);
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                res = Math.max(res, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            res = Math.max(res, heights[stack.pop()] * (heights.length - stack.peek() - 1));
        }
        return res;
    }

    /*public int largestRectangleArea(int[] heights) {
        int len = heights.length, top = -1, max = 0;
        int[] stack = new int[len];
        for (int i = 0; i < len; i++) {
            // 栈顶元素和第二个元素之间的所有高度，均大于栈顶元素
            // 所以对于栈顶元素，其左边界为第二个元素的位置 + 1
            while (top != -1 && heights[stack[top]] >= heights[i]) {
                int height = heights[stack[top]];
                top--;
                int width = top == -1 ? i : i - stack[top] - 1;
                max = Math.max(max, height * width);
            }
            stack[++top] = i;
        }
        while (top != -1) {
            int height = heights[stack[top]];
            top--;
            int width = top == -1 ? len : len - stack[top] - 1;
            max = Math.max(max, height * width);
        }
        return max;
    }*/

    public int maximalRectangle(String[] matrix) {
        // 矩阵中求最大矩阵
        // 二维 -> 一维
        // 每一行为底，连续的 1 为高，求解最大面积（水桶）
        if (matrix.length == 0 || matrix[0].length() == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length(), res = 0;
        int[] height = new int[n];
        for (String str : matrix) {
            for (int j = 0; j < n; j++) {
                // 这里具有继承上一次的效果
                if (str.charAt(j) == '1') {
                    height[j]++;
                } else {
                    height[j] = 0;
                }
            }
            res = Math.max(res, largestRectangleArea(height));
        }
        return res;
    }

    private int largestRectangleArea(int[] height) {
        int top = -1, max = 0, ind = 0;
        int len = height.length;
        int[] left = new int[len];
        for (int i = 0; i < len; i++) {
            // 栈顶元素和第二个元素之间的所有元素均大于栈顶元素
            // 所以对于以栈顶元素作为高的矩阵，其左边界应该为第二个元素下标 + 1
            while (top != -1 && height[left[top]] >= height[i]) {
                int h = height[left[top--]];
                int w =top == -1 ? i : i - left[top] - 1;
                max = Math.max(max, h * w);
            }
            left[++top] = i;
        }
        while (top != -1) {
            int h = height[left[top--]];
            int w =top == -1 ? len : len - left[top] - 1;
            max = Math.max(max, h * w);
        }
        return max;
    }
}